{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Odd Binary Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumOddBinaryNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大二进制奇数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>二进制</strong> 字符串 <code>s</code> ，其中至少包含一个 <code>'1'</code> 。</p>\n",
    "\n",
    "<p>你必须按某种方式 <strong>重新排列</strong> 字符串中的位，使得到的二进制数字是可以由该组合生成的 <strong>最大二进制奇数</strong> 。</p>\n",
    "\n",
    "<p>以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。</p>\n",
    "\n",
    "<p><strong>注意 </strong>返回的结果字符串 <strong>可以</strong> 含前导零。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"010\"\n",
    "<strong>输出：</strong>\"001\"\n",
    "<strong>解释：</strong>因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 \"001\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0101\"\n",
    "<strong>输出：</strong>\"1001\"\n",
    "<strong>解释：</strong>其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 \"100\" 。所以答案是 \"1001\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code> 仅由 <code>'0'</code> 和 <code>'1'</code> 组成</li>\n",
    "\t<li><code>s</code> 中至少包含一个 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-odd-binary-number](https://leetcode.cn/problems/maximum-odd-binary-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-odd-binary-number](https://leetcode.cn/problems/maximum-odd-binary-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"010\"', '\"0101\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOddBinaryNumber(self, s: str) -> str:\n",
    "        n_ones: int = sum(int(digit) for digit in s)\n",
    "        return \"\".join([(\"1\" * (n_ones - 1)), (\"0\" * (len(s) - n_ones)), \"1\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOddBinaryNumber(self, s: str) -> str:\n",
    "        # 计算字符串中 '1' 的数量\n",
    "        count_of_ones = s.count('1')\n",
    "        \n",
    "        # 如果字符串中没有 '1'，则返回 '0'\n",
    "        if count_of_ones == 0:\n",
    "            return '0'\n",
    "        \n",
    "        # 将所有的 '1' 移动到字符串的前面\n",
    "        result = '1' * (count_of_ones - 1)\n",
    "        \n",
    "        # 将所有的 '0' 移动到字符串的后面\n",
    "        result += '0' * (len(s) - count_of_ones)\n",
    "        \n",
    "        # 确保最后一位是 '1'\n",
    "        result += '1'\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOddBinaryNumber(self, s: str) -> str:\n",
    "        n1 = s.count('1')\n",
    "        n0 = len(s) - n1\n",
    "        if n1 == 1:\n",
    "            return n0*'0'+'1'\n",
    "        return (n1-1)*'1'+n0*'0'+'1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOddBinaryNumber(self, s: str) -> str:\n",
    "        cnt1 = s.count('1')\n",
    "        cnt0 = len(s) - cnt1\n",
    "        return '1' * (cnt1 - 1) + '0' * cnt0 + '1'"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
